7、爬山
题目 爬山
思路分析
模拟 贪心 堆
hack题 被选手发现有个数据能卡正解 笑了
代码实现
/*
有点像砍竹子
x轴上 n座山 每座山高为hi 从左到右花费的体力 前缀和
可以降低某座山的高度为
(1) 下取整floor 的根号h floor(sqrt(hi)) 有P次
(2) 下取整的 二分之h floor(hi/2) 有Q次
每座山都可以无限次做 但限制在于魔法的可用次数
如果两种次数是一起算的 就直接贪心 每次对最高的做 并且做 max( floor(sqrt(hi)) , floor(hi/2) )
但两种次数分开算 就需要抉择 可能是dp
但这个数据范围也不像是能dp
直接贪心做了 每次对最高的做 选两个方案里最优的做（有的话就做最优的 没有的话 另一种也是当前最优了）
前缀和跟差分能用吗
用：
前缀和预处理在读入的时候做
砍去山等于 做一个差分 可是差分数组要从前缀和数组里构造出来 一层for
差分完后得到原答案 又得做一遍前缀和 二层for
不用：
直接读入山
砍去山
累加 一层for
没必要用前缀和 负优化
每次找最大的山
在h[]数组保序的基础上(好像不需要存 答案是累计 顺序无关紧要） 用优先队列维护
直接用优先队列存所有的山的高度 每次取出最高的山 选择做法 再把做完的放回优先队列
*/
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int n,P,Q;
priority_queue<int> h;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>P>>Q;
while(n--){
int x;cin>>x;
h.push(x);
}
while(Q || P){
// cout<<h.top()<<endl; h.pop();
int curh=h.top();h.pop();
// cout<<"当前最高: "<<curh<<endl;
int choice1=floor(sqrt(curh));
int choice2=floor(curh/2);
int well=min(choice1,choice2);
if(well==choice1){//如果更大的是第一种操作
if(P){//且P存在
h.push(choice1);
P--;
}
else if(Q){//P操作次数没了 退而求其次 若Q存在 做Q
h.push(choice2);
Q--;
}
else{//全操作完了 break;
break;
}
}
else if(well==choice2){
if(Q){
h.push(choice2);
Q--;
}
else if(P){
h.push(choice1);
P--;
}
else{//全操作完了 break;
break;
}
}
}
long long res=0;
while(!h.empty()){
// cout<<h.top()<<" ";
res+=h.top();
h.pop();
}
cout<<res;
return 0;
}
💬 评论